package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2021/12/3 10:11 下午
 */
public class MaximizeSumOfArrayAfterKNegations {

    /**
     * 贪心算法
     * 贪心策略如下：
     * 1. 先将负数反转(依次从最小的负数反转)
     *      如果还有剩余次数，判断剩余次数是否为奇数
     *          如果为奇数则将现有的最小整数，反转为负数
     *          如果为偶数，直接求出现在数据的总和（因为可以在同一个数上反复反转）
     *
     *      如果没有剩余次数，直接求出现在数据的总和
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        int len = nums.length;
        /**
         * 优先队列获取的元素，是通过排序结果的顺序决定的，排序后结果的第一个元素优先级最高，最后一个元素优先级最低
         */
        Queue<Integer> negations = new PriorityQueue<>();
        int sum = 0, minValue = 101;
        for (int i = 0; i < len; i++) {
            if (nums[i] < 0) {
                negations.offer(nums[i]);
            } else {
                if (nums[i] < minValue) {
                    minValue = nums[i];
                }
            }
            sum += nums[i];
        }

        System.out.println("sum = " + sum + " minValue = " + minValue);

        int negationSize = negations.size();
        if (negationSize <= k) {
            while (!negations.isEmpty()) {
                Integer peekValue = -negations.poll();
                System.out.println("peekValue = " + peekValue);
                if (peekValue < minValue) {
                     minValue = peekValue;
                }
                sum += (peekValue << 1);
                k--;
            }
            if ((k&1) == 1) {
                sum -= (minValue << 1);
            }
        } else {
            while (k > 0) {
                k--;
                Integer peekValue = -negations.poll();
                sum += (peekValue << 1);

                System.out.println("peekValue = " + peekValue);
            }
        }

        return sum;
    }
}
